#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<vector>

using namespace std;

//string longestPalindrome(string s) {
//    int n = s.size();
//    auto extend = [&](int left, int right) {
//        while (left >= 0 && right < n && s[left] == s[right])
//        {
//            left--;
//            right++;
//        }
//        return make_pair(left + 1, right - 1);
//    };
//
//    int start = 0, end = 0;
//    for (int i = 0; i < n; i++)
//    {
//        auto p1 = extend(i, i);
//        auto p2 = extend(i, i + 1);
//
//        if (p1.second - p1.first > end - start)
//        {
//            start = p1.first;
//            end = p1.second;
//        }
//        if (p2.second - p2.first + 1 > end - start)
//        {
//            start = p2.first;
//            end = p2.second;
//        }
//    }
//    return s.substr(start, end - start + 1);
//}

string longestPalindrome(string s) {
    int n = s.size();
    vector<vector<bool>> f(n, vector<bool>(n));
    int len = 1, begin = 0;
    for (int i = n - 1; i >= 0; i--)
    {
        for (int j = i; j < n; j++)
        {
            if (s[i] == s[j])
                f[i][j] = i + 1 < j ? f[i + 1][j - 1] : true;
            if (f[i][j] && j - i + 1 > len)
                len = j - i + 1, begin = i;
        }
    }
    return s.substr(begin, len);
}